Location-based social network applications have become highly popular over the world. Increasing number of people is using Global Positioning System (GPS)-enabled devices to log their outdoor locations and activities. It is also getting very common for people to share information about their current locations and activities with their friends. This shared information is expected to give significant impact in social networks. Recent research has shown that the mobility patterns of individuals may be shaped by their social relationships. Likewise, human trajectories may be used to infer social ties of people in terms of relationships among individuals. For example, social ties are usually inferred by the similarity of individuals in both spatial and temporal dimensions according to their location histories.
Generally, it is impractical to discover social ties by using accurate geographic locations, because it may cause a privacy leakage. As location information is very useful privacy information, an untrusted application server may save users' location data and leak them to third parties that create privacy risks. Spatial cloaking is a common technique for providing location privacy. The cloaked trajectories can reflect certain regularities of the human mobility with inexact location information, while avoiding the risk of leaking accurate geographic locations. However, the cloaked trajectories are imprecise, making it more difficult to analyze trajectories for further inferring social ties.
Thus, it would be advancement in the art to provide an approach to discover social ties from cloaked trajectories efficiently and precisely.